#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1005000 + 1;
int isPrime[N];
int prime[N], pcnt;
int factor[1000];

int f(int n) {
    if (isPrime[n]) {
        return n - 1;
    }
    int fcnt = 0;
    int nn = n; //cache
    int ans = 0;
    for (int i = 0; i < pcnt; i++) {
        while (n % prime[i] == 0) {
            n /= prime[i];
            if (fcnt == 0 || factor[fcnt - 1] != prime[i]) {
                factor[fcnt++] = prime[i];
            }
        }
        if (isPrime[n] || n == 1) {
            if (n != 1) factor[fcnt++] = n;
            break;
        }
    }
    for (int i = 1; i < (1 << fcnt); i++) { // mask
        int multiple = 1;
        int bitCount = __builtin_popcount(i);
        for (int j = 0; j < fcnt; j++) {
            if (i & (1 << j)) {
                multiple *= factor[j];
            }
        }
        int multipleCount = nn / multiple - (nn % multiple);
        if (bitCount & 1) {
            ans += multipleCount;
        } else {
            ans -= multipleCount;
        }
    }
    return nn - ans;
}

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return r;
}

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int gg(int a, int n, int b, int m) {
    if ((b - a) % gcd(n, -m) != 0) {
        return 0;
    }

    int x, y;
    exgcd(n, -m, x, y);
    int t = -m / gcd(n, -m);
    x = (x % t + t) % t;
    return x;
}

int g(int n, int m) {
    int fn = f(n);
    int fm = f(m);
    //
    return gg(fn, n, fm, m);
}

int main()
{
    for (int i = 0; i < N; i++) isPrime[i] = 1;
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i < N; i++) {
        if (isPrime[i]) {
            prime[pcnt++] = i;
            for (int j = i + i; j < N; j += i) {
                isPrime[j] = 0;
            }
        }
    }

    long long ans = 0;
    for (int n = 1000000; n < N - 1; n++) {
        for (int m = n + 1; m < N - 1; m++) {
            ans += g(n, m);
            cout << ans << ' ' << n << ' ' << m << endl;
        }
    }

    cout << ans << endl;
    return 0;
}
